package SwordFingerOffer;

import java.util.*;

public class Q34_TreePathSum {

    List<List<Integer>> ans = new LinkedList<>();
    //输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。
    //路径规定从树的根节点开始到"叶子"节点

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        LinkedList<Integer> list = new LinkedList<>();
        process(root, target, list, 0);
        return ans;
    }

    //此方法支持从根节点开始到任意节点
    public void process(TreeNode root, int target, LinkedList<Integer> list, int Sum) {

        if (root == null){
            return;
        }

        Sum += root.val;
        list.addLast(root.val);

        if (Sum == target){
            List<Integer> tmp = new LinkedList<>(list);
            ans.add(tmp);
        }
        process(root.left, target, list, Sum);
        process(root.right, target, list, Sum);
        //恢复现场
        Sum -= root.val;
        list.removeLast();
    }

    //专门针对根到叶子节点
    public void process_1(TreeNode root, int target, LinkedList<Integer> list, int Sum) {

        if (root == null){
            return;
        }

        Sum += root.val;
        list.addLast(root.val);

        if (Sum == target && root.left == null && root.right == null){
            List<Integer> tmp = new LinkedList<>(list);
            ans.add(tmp);
        }
        process(root.left, target, list, Sum);
        process(root.right, target, list, Sum);
        Sum -= root.val;
        list.removeLast();
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(-11);
        root.right.left.left = new TreeNode(1);
        root.right.left.left.left = new TreeNode(-1);
        root.right.right = new TreeNode(7);
        Q34_TreePathSum fun = new Q34_TreePathSum();
        System.out.println(fun.pathSum(root,12));
    }
}
